package B.链表;

import java.util.HashMap;
import java.util.Map;

public class _876_链表的中间结点 {
    /**
     * 自解：借助map 计数
     * 空间时间复杂度都是N
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {

        ListNode count = head;
        Map<Integer,ListNode> map = new HashMap<>();
        for (int i=0;i<100 && head!=null;i++){
            map.put(i,head);
            head=head.next;//head为null时 不存 直接就跳出了
        }
        for (int i=0;i<Math.ceil(map.size()/2);i++){
            count = count.next;
        }
        return count;
    }
    /**
     * 题解1-优化空间复杂度
     * 对链表进行两次遍历。
     * 第一次遍历时，我们统计链表中的元素个数 N；
     * 第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可
     */
    public ListNode middleNode1(ListNode head) {
        int N=0;
        ListNode node = head;
        while (node != null){
            node = node.next;
            N++;
        }

        for (int i=0;i<Math.ceil(N/2);i++){
            head = head.next;
        }

        return head;
    }

    /**
     * 题解2：用双指针 一个逐个移动 另一个跳两个运动 这样快的那个到终点了 慢的那个就在一半 nb！
     *
     */
    public ListNode middleNode2(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}
